1147B - Chladni Figure - CodeForces Solution

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <sstream>
#include <assert.h>

using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define debug(a) cout<<#a<<"="<<a<<endl
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair<int,int> PII;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll qmi(ll a,ll k,ll p){ll res=1%p;a%=p;while(k){if(k&1)res=res*a%p;k>>=1;a=a*a%p;}return res;}

const int N = 2e5+10;

PII a[N];

int main()
{
	IOS;
	int n,m;
	cin >> n >> m;
	int h1 = 0;
	rep(i,1,m){
		int x,y;
		cin >> x >> y;
		a[i] = {x%n,y%n};
		if(a[i].fi > a[i].se)
			swap(a[i].fi,a[i].se);
		h1 ^= a[i].first*100000+a[i].second;
	}
	
	for(int i=1;i*i<=n;i++){
		if(n%i == 0){
			int h2=0;
			rep(j,1,m){
				if((a[j].first+i)%n > (a[j].second+i)%n)
					swap(a[j].fi,a[j].se);
				h2 ^= (a[j].fi+i)%n*100000+(a[j].se+i)%n;
			}
			if(h2 == h1){
				cout << "YES" << endl;
				return 0; 
			}
			if(i != n/i && i!=1){
				h2 = 0;
				rep(j,1,m){
					if((a[j].first+n/i)%n > (a[j].second+n/i)%n)
						swap(a[j].fi,a[j].se);
					h2 ^= (a[j].fi+n/i)%n*100000+(a[j].se+n/i)%n;
				}
				if(h2 == h1){
					cout << "YES" << endl;
					return 0; 
				}
			}
		}
	}
	cout << "NO" << endl;
	
	return 0;
}